A graph-theoretical approach for the computation of connected iso-surfaces based on volumetric data

摘要

The existing combinatorial methods for iso-surface computation are efficientfor pure visualization purposes, but it is known that the resultingiso-surfaces can have holes, and topological problems like missing or wrongconnectivity can appear. To avoid such problems, we introduce agraph-theoretical method for the computation of iso-surfaces on cuboid meshesin $\mathbb{R}^3$. The method for the generation of iso-surfaces employslabeled cuboid graphs $G(V,E,\mathcal{F})$ such that $V$ is the set of verticesof a cuboid $C\subset\mathbb{R}^3$, $E$ is the set of edges of $C$ and$\mathcal{F}\,:\,V\rightarrow [0,1]$. The nodes of $G$ are weighted by thevalues of $\mathcal{F}$ which represents the volumetric information, e.g.\ froma Volume of Fluid method. Using a given iso-level $c\in (0,1)$, we first obtainall iso-points, i.e.\ points where the value $c$ is attained by theedge-interpolated $\mathcal{F}$-field. The iso-surface is then built fromiso-elements which are composed of triangles and are such that their polygonalboundary has only iso-points as vertices. All vertices lie on the faces of asingle mesh cell. We give a proof that the generated iso-surface is connected up to theboundary of the domain and it can be decomposed into different orientedcomponents. Two different components may have discrete points or line segmentsin common. The graph-theoretical method for the computation of iso-surfacesdeveloped in this paper enables to recover local information of the iso-surfacethat can be used e.g.\ to compute discrete mean curvature and to solve surfacePDEs. Concerning the computational effort, the resulting algorithm is asefficient as existing combinatorial methods.